/*
 * 数据结构模板库 - 常用高效数据结构实现
 * 使用场景: 需要特殊数据结构优化算法性能的题目
 * 包含: 并查集、线段树、树状数组、字典树、单调栈队列、高级堆等
 */

#pragma once
#include "basic_template.hpp"

// 并查集 (Union-Find) - 处理动态连通性问题
// 使用场景: 判断图的连通性、最小生成树、动态连通性查询
// 时间复杂度: 几乎O(1)的查询和合并操作
// 典型应用: 朋友圈问题、岛屿数量、网络连接
class UnionFind
{
private:
    vector<int> parent, rank;
    int components;

public:
    UnionFind(int n) : parent(n), rank(n, 0), components(n)
    {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x)
    {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y)
    {
        int px = find(x), py = find(y);
        if (px == py)
            return false;

        if (rank[px] < rank[py])
            swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py])
            rank[px]++;
        components--;
        return true;
    }

    bool connected(int x, int y)
    {
        return find(x) == find(y);
    }

    int get_components() const
    {
        return components;
    }
};

// 线段树 (Segment Tree) - 支持区间查询和区间修改
// 使用场景: 区间求和、区间最值、区间修改等操作
// 时间复杂度: O(log n)的查询和修改
// 典型应用: 区间求和、RMQ问题、懒惰传播
// 注意: 这里实现的是支持区间加法和区间求和的版本
class SegmentTree
{
private:
    vector<ll> tree, lazy;
    int n;

    void push(int node, int start, int end)
    {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void update_range(int node, int start, int end, int l, int r, ll val)
    {
        push(node, start, end);
        if (start > r || end < l)
            return;

        if (start >= l && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }

        int mid = (start + end) / 2;
        update_range(2 * node, start, mid, l, r, val);
        update_range(2 * node + 1, mid + 1, end, l, r, val);

        push(2 * node, start, mid);
        push(2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    ll query_range(int node, int start, int end, int l, int r)
    {
        if (start > r || end < l)
            return 0;
        push(node, start, end);

        if (start >= l && end <= r)
            return tree[node];

        int mid = (start + end) / 2;
        return query_range(2 * node, start, mid, l, r) +
               query_range(2 * node + 1, mid + 1, end, l, r);
    }

public:
    SegmentTree(const vector<ll> &arr)
    {
        n = (int)arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }

    void build(const vector<ll> &arr, int node, int start, int end)
    {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    void update(int l, int r, ll val)
    {
        update_range(1, 0, n - 1, l, r, val);
    }

    ll query(int l, int r)
    {
        return query_range(1, 0, n - 1, l, r);
    }
};

// 树状数组 (Fenwick Tree / Binary Indexed Tree) - 高效的前缀和数据结构
// 使用场景: 动态维护前缀和、单点修改区间查询
// 时间复杂度: O(log n)的修改和查询
// 典型应用: 逆序对统计、动态前缀和、二维偏序
// 优点: 代码简单，常数小，空间效率高
class FenwickTree
{
private:
    int n;
    vector<ll> tree;

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void update(int idx, ll val)
    {
        for (++idx; idx <= n; idx += idx & -idx) {
            tree[idx] += val;
        }
    }

    ll query(int idx)
    {
        ll sum = 0;
        for (++idx; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }

    ll range_query(int l, int r)
    {
        return query(r) - (l > 0 ? query(l - 1) : 0);
    }
};

// 字典树 (Trie) - 高效的字符串集合数据结构
// 使用场景: 字符串匹配、前缀查询、自动补全、单词统计
// 时间复杂度: O(m)的插入和查询，m为字符串长度
// 典型应用: 前缀匹配、单词搜索、IP路由、拼写检查
// 优点: 公共前缀共享存储，查询效率高
class Trie
{
private:
    struct TrieNode {
        unordered_map<char, TrieNode *> children;
        bool is_end;
        int count;

        TrieNode() : is_end(false), count(0) {}
    };

    TrieNode *root;

public:
    Trie()
    {
        root = new TrieNode();
    }

    void insert(const string &word)
    {
        TrieNode *curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                curr->children[c] = new TrieNode();
            }
            curr = curr->children[c];
            curr->count++;
        }
        curr->is_end = true;
    }

    bool search(const string &word)
    {
        TrieNode *curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                return false;
            }
            curr = curr->children[c];
        }
        return curr->is_end;
    }

    bool starts_with(const string &prefix)
    {
        TrieNode *curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) {
                return false;
            }
            curr = curr->children[c];
        }
        return true;
    }

    int count_prefix(const string &prefix)
    {
        TrieNode *curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) {
                return 0;
            }
            curr = curr->children[c];
        }
        return curr->count;
    }
};

// 单调栈
template <typename T>
class MonotonicStack
{
private:
    stack<pair<T, int>> st;
    bool increasing;

public:
    MonotonicStack(bool inc = true) : increasing(inc) {}

    void push(T val, int idx)
    {
        while (!st.empty() &&
               (increasing ? st.top().first >= val : st.top().first <= val)) {
            st.pop();
        }
        st.push({val, idx});
    }

    pair<T, int> top()
    {
        return st.empty() ? make_pair(T(), -1) : st.top();
    }

    bool empty()
    {
        return st.empty();
    }

    void clear()
    {
        while (!st.empty())
            st.pop();
    }
};

// 单调队列
template <typename T>
class MonotonicQueue
{
private:
    deque<pair<T, int>> dq;
    bool increasing;

public:
    MonotonicQueue(bool inc = true) : increasing(inc) {}

    void push(T val, int idx)
    {
        while (!dq.empty() &&
               (increasing ? dq.back().first >= val : dq.back().first <= val)) {
            dq.pop_back();
        }
        dq.push_back({val, idx});
    }

    void pop_expired(int min_idx)
    {
        while (!dq.empty() && dq.front().second < min_idx) {
            dq.pop_front();
        }
    }

    pair<T, int> front()
    {
        return dq.empty() ? make_pair(T(), -1) : dq.front();
    }

    bool empty()
    {
        return dq.empty();
    }
};

// 可持久化数组 (版本控制数组) - 支持历史版本查询的数组
// 使用场景: 需要查询历史状态、撤销操作、函数式编程
// 时间复杂度: O(log n)的修改和查询
// 典型应用: 可持久化线段树、主席树、历史查询
// 特点: 每次修改创建新版本，所有历史版本都可访问
// 注意: 这是一个高级数据结构，适用于特殊的竞赛题目
template <typename T>
class PersistentArray
{
private:
    struct Node {
        T val;
        Node *left;
        Node *right;
        Node(T v = T(), Node *l = nullptr, Node *r = nullptr) : val(v), left(l), right(r) {}
    };

    vector<Node *> roots;
    int n;

    Node *build(int l, int r, const vector<T> &arr)
    {
        if (l == r) {
            return new Node(arr[l]);
        }
        int mid = (l + r) / 2;
        return new Node(T(), build(l, mid, arr), build(mid + 1, r, arr));
    }

    Node *update(Node *node, int l, int r, int pos, T val)
    {
        if (l == r) {
            return new Node(val);
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            return new Node(T(), update(node->left, l, mid, pos, val), node->right);
        } else {
            return new Node(T(), node->left, update(node->right, mid + 1, r, pos, val));
        }
    }

    T query(Node *node, int l, int r, int pos)
    {
        if (l == r) {
            return node->val;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            return query(node->left, l, mid, pos);
        } else {
            return query(node->right, mid + 1, r, pos);
        }
    }

public:
    PersistentArray(const vector<T> &arr) : n(arr.size())
    {
        roots.push_back(build(0, n - 1, arr));
    }

    void update(int version, int pos, T val)
    {
        roots.push_back(update(roots[version], 0, n - 1, pos, val));
    }

    T query(int version, int pos)
    {
        return query(roots[version], 0, n - 1, pos);
    }

    int get_version_count()
    {
        return roots.size();
    }
};

// 左偏树 (可并堆) - 支持高效合并的堆数据结构
// 使用场景: 需要频繁合并两个堆的场景
// 时间复杂度: O(log n)的插入、删除、合并操作
// 典型应用: 图论算法中的优先队列合并、并查集优化
// 特点: 相比普通堆，支持O(log n)的合并操作
// 注意: 这是小根堆实现，需要大根堆可以取负数
template <typename T>
class LeftistHeap
{
private:
    struct Node {
        T val;
        int dist;
        Node *left;
        Node *right;
        Node(T v) : val(v), dist(0), left(nullptr), right(nullptr) {}
    };

    Node *root;

    Node *merge(Node *a, Node *b)
    {
        if (!a)
            return b;
        if (!b)
            return a;

        if (a->val > b->val)
            swap(a, b);

        a->right = merge(a->right, b);

        if (!a->left || a->left->dist < a->right->dist) {
            swap(a->left, a->right);
        }

        a->dist = a->right ? a->right->dist + 1 : 0;
        return a;
    }

public:
    LeftistHeap() : root(nullptr) {}

    void push(T val)
    {
        root = merge(root, new Node(val));
    }

    T top()
    {
        return root->val;
    }

    void pop()
    {
        Node *old_root = root;
        root = merge(root->left, root->right);
        delete old_root;
    }

    bool empty()
    {
        return root == nullptr;
    }

    void merge_with(LeftistHeap &other)
    {
        root = merge(root, other.root);
        other.root = nullptr;
    }
};

// 斜堆 (自调整堆)
template <typename T>
class SkewHeap
{
private:
    struct Node {
        T val;
        Node *left;
        Node *right;
        Node(T v) : val(v), left(nullptr), right(nullptr) {}
    };

    Node *root;

    Node *merge(Node *a, Node *b)
    {
        if (!a)
            return b;
        if (!b)
            return a;

        if (a->val > b->val)
            swap(a, b);

        a->right = merge(a->right, b);
        swap(a->left, a->right);

        return a;
    }

public:
    SkewHeap() : root(nullptr) {}

    void push(T val)
    {
        root = merge(root, new Node(val));
    }

    T top()
    {
        return root->val;
    }

    void pop()
    {
        Node *old_root = root;
        root = merge(root->left, root->right);
        delete old_root;
    }

    bool empty()
    {
        return root == nullptr;
    }

    void merge_with(SkewHeap &other)
    {
        root = merge(root, other.root);
        other.root = nullptr;
    }
};
